/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Manhattan;

/**
 *
 * @author SHAI
 */
import ia1_practica2.mainFrame;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Manhattan {

    String str = ""; // initial state
    String goal = ""; //goal state
    PriorityQueue<StateOrder> queue;
    Map<String, Integer> levelDepth;
    Map<String, String> stateHistory;
    int nodes = 0; //counter for node generation
    int limit = 100; //counter for limit
    int unique = -1;//counter for uniq state
    int newValue; //counter depth limit
    int a; //position of blank
    int h; //heuristic
    String currState;
    boolean solution = false;
    int countStep=0;

    public Manhattan(String str, String goal,int limit) {
        queue = new PriorityQueue<StateOrder>();
        levelDepth = new HashMap<String, Integer>();
        stateHistory = new HashMap<String, String>();
        this.str = str;
        this.goal = goal;
        this.limit = limit;
        addToQueue(str, null);
    }

    public void doSearch() {

        while (!queue.isEmpty()) {

            currState = queue.poll().toString();

            if (currState.equals(goal)) {
                solution = true;
                printSolution(currState);
                break;
            }
            if (levelDepth.get(currState) == limit) {
                solution = false;
                printSolution(currState);
                break;
            } else {
                a = currState.indexOf("0");
//left
                while (a != 0 && a != 3 && a != 6) {
                    String nextState = currState.substring(0, a - 1)
                            + "0" + currState.charAt(a - 1)
                            + currState.substring(a + 1);
                    addToQueue(nextState, currState);
                    nodes++;
                    break;
                }
//up
                while (a != 0 && a != 1 && a != 2) {
                    String nextState = currState.substring(0, a - 3)
                            + "0" + currState.substring(a - 2, a)
                            + currState.charAt(a - 3)
                            + currState.substring(a + 1);
                    addToQueue(nextState, currState);
                    nodes++;
                    break;
                }
//right
                while (a != 2 && a != 5 && a != 8) {
                    String nextState = currState.substring(0, a)
                            + currState.charAt(a + 1)
                            + "0" + currState.substring(a + 2);
                    addToQueue(nextState, currState);
                    nodes++;
                    break;
                }

//down
                while (a != 6 && a != 7 && a != 8) {
                    String nextState = currState.substring(0, a)
                            + currState.substring(a + 3, a + 4)
                            + currState.substring(a + 1, a + 3)
                            + "0" + currState.substring(a + 4);
                    addToQueue(nextState, currState);
                    nodes++;
                    break;
                }

            }
        }

        if (solution) {
            System.out.println("Existe Solucion!");
        } else {
            System.out.println("Solution not yet found! My suggestion are:");
            System.out.println("1. Try to increse level depth limit ");
            System.out.println("2. Use other heuristc ");
            System.out.println("3. Maybe it is physically impossible");
            System.out.println("nodos creados: " + nodes);
            System.out.println("Nodos Unicos Generados: " + unique);
            System.out.println(levelDepth.get(currState) + " pasos");
        }

    }

    private void addToQueue(String newState, String oldState) {
        if (!levelDepth.containsKey(newState)) {// check repeated state
            newValue = oldState == null ? 0 : levelDepth.get(oldState) + 1;
            unique++;
            levelDepth.put(newState, newValue);
            h = calcManhattan(newState, goal); // calculate heuristic from newstate
//h= 0;
            queue.add(new StateOrder(h, newState));//add to priority queue
            stateHistory.put(newState, oldState);
        }
    }

    private int calcManhattan(String currState, String goalState) {
//lookup table for manhattan distance
        int[][] manValue = {
            {0, 1, 2, 1, 2, 3, 2, 3, 4},
            {1, 0, 1, 2, 1, 2, 3, 2, 3},
            {2, 1, 0, 3, 2, 1, 4, 3, 2},
            {1, 2, 3, 0, 1, 2, 1, 2, 3},
            {2, 1, 2, 1, 0, 1, 2, 1, 2},
            {3, 2, 1, 2, 1, 0, 3, 2, 1},
            {2, 3, 4, 1, 2, 3, 0, 1, 2},
            {3, 2, 3, 2, 1, 2, 1, 0, 1},
            {4, 3, 2, 3, 2, 1, 2, 1, 0},};
//calculate manhattan distance
        int heu = 0;
        int result = 0;
//String a = null;
        for (int i = 1; i < 9; i++) {
            heu = manValue[currState.indexOf(String.valueOf(i))][goalState.indexOf(String.valueOf(i))];
            result = result + heu;
        }
        return result;
    }

    private void printSolution(String currState) {
        if (solution) {
            countStep = levelDepth.get(currState);
            System.out.println("Solucion encontrada en: " + levelDepth.get(currState) + " pasos");
            System.out.println("Nodos Generados:        " + nodes);
            System.out.println("Nodos Unicos Generados: " + unique);
        } else {
            System.out.println("Solucion no Encontrada!");
            System.out.println("Se alcanzo el Limite de iteracciones!");
            System.out.println("Nodos generados:        " + nodes);
            System.out.println("Nodos Unicos Generados: " + unique);
            
            mainFrame.printArea("Solucion no Encontrada!");
            mainFrame.printArea("Se alcanzo el Limite de iteracciones!");
            mainFrame.printArea("");
        }
        String ruta = "";
        String traceState = currState;
        while (traceState != null) {
            System.out.println(traceState + " del paso " + levelDepth.get(traceState));
            mainFrame.printArea(traceState + " del paso " + levelDepth.get(traceState));
            try {
                for (int z = 0; z < 9; z++) {
                    System.out.print(" " + String.valueOf(traceState.charAt(z)) + " ");
                    ruta = ruta + " " + String.valueOf(traceState.charAt(z)) + " ";
                    if ((z + 1) % 3 == 0) {
                        System.out.println();
                        mainFrame.printArea(ruta);
                        ruta = "";
                    }
                }
            } catch (NullPointerException e) {
            }
            traceState = stateHistory.get(traceState);
        }

    }

    public int getNodes() {
        return nodes;
    }

    public int getUnique() {
        return unique;
    }

    public int getH() {
        return h;
    }

    public int getCountStep() {
        return countStep;
    }
}

//end code
